package 算法.leetcode.offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author lchenglong
 * @date 2022/4/28
 */
public class Offer36 {

    public static void main(String[] args) {
        Node _4 = new Node(4);
        Node _2 = new Node(2);
        Node _5 = new Node(5);
        Node _1 = new Node(1);
        Node _3 = new Node(3);
        _4.right=_5;
        _4.left = _2;
        _2.right= _3;
        _2.left = _1;
        Offer36 instance= new Offer36();
        Node ans = instance.treeToDoublyList(_4);
        System.out.println(ans);
    }
    Node head = new Node();
    Node cursor = head;
    Queue<Node> visited = new LinkedList<>();
    public Node treeToDoublyList(Node root) {
        dfs(root);
        for (int i=0,size=visited.size();i<size;i++) {
            Node node = visited.poll();
            if (i == 0){
                // head->node
                // null<-node->null;
                // cursor = node
                head.right = node;
                cursor = node;
                node.right = null;
                node.left = null;
            } else if (i==size-1){
                cursor.right = node;
                node.left = cursor;
                node.right = head.right;
                cursor = cursor.right;
            }else {
                // cursor->node
                // cursor<-node->null
                cursor.right = node;
                node.left = cursor;
                node.right = null;
                cursor = cursor.right;
            }

        }
        head.right.left = cursor;
        return head.right;
    }

    void dfs(Node node) {
        if (node == null)return;
        // 左子树
        dfs(node.left);
        // 根
        visited.add(node);
        // 右子树
        dfs(node.right);
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
